/* s^2 - testing the sHT_bit_test function
   Copyright (C) 2018 Ariadne Devos

   This program is free software: you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation, either version 3 of the License, or
   (at your option) any later version.

   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.

   You should have received a copy of the GNU General Public License
   along with this program.  If not, see <http://www.gnu.org/licenses/>. */

#include <sHT/bitvec.h>
#include <sHT/index.h>
#include <sHT/test.h>

#include <limits.h>
#include <stddef.h>
#include <stdio.h>
#include <stdint.h>
#include <string.h>
#include <sys/mman.h>
#include <unistd.h>

/* This tests that:
   * the bit vector may be unaligned,
   * the bit order is correct.
   * the vector may be longer than 64-bits
   * no memory before or after the bitvector is accessed
     (on virtual-memory systems)
   * the bitvector may be read-only
     (on virtual-memory systems).

   The correctness of the bit vector is verified with a typical
   reference implementation, and a trivial table lookup. -- s^2
   does not always use the reference implementation, on x86, it
   uses a special instruction.

   Very hypothetical TODO: this test could be speculatively unsafe. */

/* A random bitvector, expanded to @var{reference}. */
const uint8_t compact[] = {
	0b00110101,

	0b11010101,
	0b01101110,
	0b10110110,
	0b11000101,

	0b00100111,
	0b00000010,
	0b10011001,
	0b00000000,

	0b10001111,
	0b10100001,
	0b11001001,
	0b00111001,

	0b11100001,
	0b10011110,
	0b10101010,
	0b00110101,
};

static const _Bool reference[] = {
	1, 0, 1, 0, 1, 1, 0, 0,

	1, 0, 1, 0, 1, 0, 1, 1,
	0, 1, 1, 1, 0, 1, 1, 0,
	0, 1, 1, 0, 1, 1, 0, 1,
	1, 0, 1, 0, 0, 0, 1, 1,

	1, 1, 1, 0, 0, 1, 0, 0,
	0, 1, 0, 0, 0, 0, 0, 0,
	1, 0, 0, 1, 1, 0, 0, 1,
	0, 0, 0, 0, 0, 0, 0, 0,

	1, 1, 1, 1, 0, 0, 0, 1,
	1, 0, 0, 0, 0, 1, 0, 1,
	1, 0, 0, 1, 0, 0, 1, 1,
	1, 0, 0, 1, 1, 1, 0, 0,

	1, 0, 0, 0, 0, 1, 1, 1,
	0, 1, 1, 1, 1, 0, 0, 1,
	0, 1, 0, 1, 0, 1, 0, 1,
	1, 0, 1, 0, 1, 1, 0, 0,
};

#define reference_test(i, vec) ((_Bool) ((vec)[(i) / 8] & (1 << ((i) % 8))))

int
main(void)
{
	/* Make three different tables:
	  one at the end of a page,
	  one the beginning of a page,
	  and the original table.

	  Allocate three pages, write the bitvector,
	  then disallow access to the start and the end
	  and only allow read access to the middle.
	  If the bit vector code then tries to trespass the boundary,
	  or write to the bitvector, a segfault results.

	  x86 has bit test instructions that change the bit vector,
	  so it makes sense to require read-only access. */
	unsigned long page_size;
#ifdef PAGE_SIZE
	page_size = PAGE_SIZE;
#else
	page_size = sysconf(_SC_PAGESIZE);
	if (page_size == (unsigned long) (long) -1) {
		perror("not posix: _SC_PAGESIZE");
		return 2;
	}
#endif
	if (2 * sizeof(compact) > page_size) {
		fprintf(stderr, "%s", "very small pages\n");
		return 2;
	}

	uint8_t *start = mmap(NULL, 3 * page_size, PROT_WRITE, MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
	if (sHT_eq_pointer(start, MAP_FAILED)) {
		perror("allocate memory");
		return 2;
	}
	memcpy(start + page_size, compact, sizeof(compact));
	memcpy(start + 2 * page_size - sizeof(compact), compact, sizeof(compact));
	if (mprotect(start, page_size, PROT_NONE))
		goto prot_change_error;
	if (mprotect(start + page_size, page_size, PROT_READ))
		goto prot_change_error;
	if (mprotect(start + 2 * page_size, page_size, PROT_NONE)) {
	prot_change_error:
		perror("change protections");
		return 2;
	}

	const uint8_t *vec1 = compact;
	const uint8_t *vec2 = start + page_size;
	const uint8_t *vec3 = start + 2 * page_size - sizeof(compact);

	/* Compare two implementations on the three bitvectors
	   with the reference table. */
	size_t i;
	sHT_index_iterate(i, 8 * sizeof(compact)) {
		int n = 0;
		n += reference[i];
		n += reference_test(i, vec1);
		n += sHT_bit_test(vec2, i);
		n += sHT_bit_test(vec3, i);
		if ((n != 4) && (n != 0)) {
			printf("%u: disagreement\n", i);
			return 1;
		}
	}
	return 0;
}
